#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Solution01 {
public:
    int m, n;
    // pair<int, int> CalUp(int i, int j, int k) {
    //     int x1 = max(i - k, 0);
    // }
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        m = mat.size(), n = mat[0].size();
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        // 计算点的四个点
        // 计算左上角的点和右上角的点
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x1 = max(i - k, 0), y1 = max(j - k, 0);
                int x2 = min(m - 1, i + k), y2 = min(n - 1, j + k);
                ret[i][j] = dp[x2 + 1][y2 + 1] - dp[x2 + 1][y1] - dp[x1][y2 + 1] + dp[x1][y1];
            }
        }
        return ret;
    }
};

class Solution02 {
public:
    int hammingWeight(int n) {
        int cnt = 0;
        while (n != 0) {
            cnt++;
            n &= (n - 1);
        }
        return cnt;
    }
};

class Solution03 {
public:
    int hammingWeight(int n) {
        int cnt = 0;
        while (n != 0) {
            cnt++;
            n &= (n - 1);
        }
        return cnt;
    }

    vector<int> countBits(int n) {
        vector<int> ret;
        for (int i = 0; i <= n; i++) {
            // 计算i中有几个1
            int cnt = hammingWeight(i);
            ret.emplace_back(cnt);
        }
        return ret;
    }
};

class Solution04 {
public:
    int hammingDistance(int x, int y) {
        // 计算不同位置的数目
        int cnt = 0;
        // 分别拿到1位的数据，然后对比是否相同
        for (int i = 0; i <= 31; i++) {
            int x1 = (x >> i) & 1, y1 = (y >> i) & 1;
            if (x1 != y1) cnt++;
        }
        return cnt;
    }
};

class Solution05 {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e : nums) ret ^= e;
        return ret;
    }
};

class Solution06 {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorx = 0;
        for (auto e : nums) xorx ^= e;
        int x1 = 0, y1 = 0;
        int lsb = (xorx == INT_MIN ? xorx : xorx & (-xorx));
        for (auto e : nums) {
            if (lsb & e) x1 ^= e;
            else y1 ^= e;
        }
        return {x1, y1};
    }
};

class Solution07 {
public:
    bool isUnique(string astr) {
        if (astr.size() > 26) return false;
        int bitmap = 0;
        for (auto ch : astr) {
            // 判定某个位置是否为一
            int shift = ch - 'a';
            int x = 1 << shift;
            if (x & bitmap) return false;
            else bitmap |= x;
        }
        return true;
    }
};

class Solution08 {
public:
    int missingNumber(vector<int>& nums) {
        // int ret = 0;
        // int len = nums.size();
        // for (int i = 1; i <= len; i++)
        //     ret ^= i;
        // for (auto e : nums) 
        //     ret ^= e;
        // return ret;
        int len = nums.size();
        int sum = len * (len + 1) / 2;
        for (auto e : nums) sum -= e;
        return sum;
    }
};

class Solution09 {
public:
    int getSum(int a, int b) {
        // return a + b;
        // 先找到不需要进位的，然后找到需要进位的左移一位，然后相加，知道异或为0，
        int x = a ^ b, y = (a & b) << 1;
        while (y) {
            int x1 = x ^ y, y1 = (x & y) << 1;
            x = x1, y = y1;
        }
        return x;
    }
};

int main() {


    return 0;
}